<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
const int maxt = (int)1e7;

struct tree
{
  int l, r;
};

tree t[maxt];
int tpos = 0;

int NewT( int l, int r )
{
  assert(tpos &lt; maxt);
  t[tpos].l = l;
  t[tpos].r = r;
  return tpos++;
}

struct PArray // Persistent Array
{
  int n, root;

  int Build( int n, int *a )
  {
    if (n == 1)
      return NewT(*a, *a);
    int m = n / 2;
    return NewT(Build(m, a), Build(n - m, a + m));
  }
  
  PArray( int _n, int *a ) : n(_n), root(Build(n, a)) { }
  PArray( int _n, int _root ) : n(_n), root(_root) { }
  PArray() { }

  int Get( int v, int n, int k )
  {
    if (n == 1)
      return t[v].l;
    int m = n / 2;
    return k &lt; m ? Get(t[v].l, m, k) : Get(t[v].r, n - m, k - m);
  }

  int operator [] ( int i )
  {
    return Get(root, n, i);
  }

  int Change( int v, int n, int i, int x )
  {
    if (i &lt; 0 || i &gt;= n)
      return v;
    if (n == 1)
      return NewT(x, x);
    int m = n / 2;
    return NewT(Change(t[v].l, m, i, x), Change(t[v].r, n - m, i - m, x));
  }

  PArray Change( int i, int x )
  {
    return PArray(n, Change(root, n, i, x));
  }
};

</code></pre>

</body>
</html>

<font style="visibility:hidden">
